负环

Time Limit: 100 Sec Memory Limit: 256 MB

Description

在忘记考虑负环之后，黎瑟的算法又出错了。对于边带权的有向图 G = (V, E)，请找出一个点数最小的环，使得环上的边权和为负数。保证图中不包含重边和自环。

Input

第1两个整数n, m,表示图的点数和边数。

接下来的m行，每<=三个整数ui, vi, wi，表<=有一条从ui到vi，权值为wi的有向边。

Output

仅一行一个整数，表示点数最小的环上的点数，若图中不存在负环输出0。

Sample Input

3 6
　1 2 -2
　2 1 1
　2 3 -10
　3 2 10
　3 1 -10
　1 3 10

Sample Output

2

HINT

2 <= n <= 300

0 <= m <= n^2

1 <= ui, vi <= n

|wi| <= 10^4

Main idea

给定若干单向边，找出点数最小的负环。

Solution

显然直接二分答案，用DfsSPFA限制深搜层数判断是否存在可行负环即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;

const int ONE = 305;
const int EDG = ONE*ONE;

int n,m;
int x,y,z;
int next[EDG],first[EDG],go[EDG],w[EDG],tot;
int vis[ONE],dist[ONE];
int PD;

int get()
{
    int res=1,Q=1;    char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

void Add(int u,int v,int z)
{
    next[++tot]=first[u];    first[u]=tot;    go[tot]=v;    w[tot]=z;
}

void Spfa(int u,int T,int Limit)
{
    if(PD) return;
    for(int e=first[u];e;e=next[e])
    {
        int v = go[e];
        if(dist[u]+w[e] <= dist[v])
        {
            if(vis[v]) {PD = 1; return;}
            if(T==Limit) return;
            dist[v] = dist[u] + w[e];
            vis[v] = 1;
            Spfa(v,T+1,Limit);
            vis[v] = 0;
        }
    }
}

int Check(int Limit)
{
    PD = 0;
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));  vis[i] = 1;
        memset(dist,0,sizeof(dist));
        Spfa(i,1,Limit);
        if(PD) return 1;
    }
    return 0;
}

int main()
{
    n=get();    m=get();
    for(int i=1;i<=m;i++)
    {
        x=get();    y=get();    z=get();
        Add(x,y,z);
    }

    if(!Check(n)) {printf("0"); exit(0);}

    int l=1, r=n;
    while(l < r-1)
    {
        int mid = l+r>>1;
        if(Check(mid)) r = mid;
        else l = mid;
    }

    if(Check(l)) printf("%d",l);
    else printf("%d",r);
}